package com.zrf.base.knowledge.collections;

import lombok.AllArgsConstructor;
import lombok.NoArgsConstructor;

import java.util.AbstractSequentialList;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.function.Consumer;

/**
 * 自己实现的linkedList
 *
 * @author zhouruifeng
 *         create at 2017/4/23.
 */
@NoArgsConstructor
public class MyLinkedList<T> extends AbstractSequentialList<T> implements List<T>, Deque<T>, Cloneable,
        java.io.Serializable {
    /**
     * 链表的size
     */
    private transient int size;
    /**
     * 链表的第一个节点
     */
    private transient Node<T> firstNode;
    /**
     * 链表的最后一个节点
     */
    private transient Node<T> lastNode;

    public MyLinkedList(Collection<T> collection) {
        this();
        addAll(collection);
    }

    @Override
    public ListIterator<T> listIterator(int index) {
        return new ListItr(index);
    }

    @Override
    public int size() {
        return size;
    }

    public boolean add(T t) {
        addLast(t);
        return true;
    }

    @Override
    public void add(int index, T t) {
        checkIndexForAdd(index);
        if (index == size) {
            addLast(t);
        } else if (index == 0) {
            addFirst(t);
        } else {
            Node<T> node = node(index);
            Node<T> preNode = node.preNode;

            Node<T> newNode = new Node<T>(t, preNode, node);
            preNode.nextNode = newNode;
            node.preNode = newNode;
        }
        size++;
    }

    @Override
    public void addFirst(T t) {
        Node<T> lastFirst = firstNode;
        Node<T> addNode = new Node<T>(t, null, lastFirst);
        firstNode = addNode;
        if (lastFirst != null) {
            lastFirst.preNode = addNode;
        } else {
            lastNode = addNode;
        }
        size++;
    }

    @Override
    public void addLast(T t) {
        Node<T> lastLast = lastNode;
        Node<T> addNode = new Node<T>(t, lastLast, null);
        lastNode = addNode;
        if (lastLast != null) {
            lastLast.nextNode = addNode;
        } else {
            firstNode = addNode;
        }
        size++;
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> c) {
        checkIndexForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0) {
            return false;
        }

        MyLinkedList.Node<T> needAppendNode, needInsertNode;
        if (index == size) {
            needAppendNode = lastNode;
            needInsertNode = null;
        } else {
            needInsertNode = node(index);
            needAppendNode = needInsertNode.preNode;
        }

        for (Object o : a) {
            MyLinkedList.Node<T> newNode = new MyLinkedList.Node((T) o, needAppendNode, null);
            if (needAppendNode == null) {
                firstNode = newNode;
            } else {
                needAppendNode.nextNode = newNode;
            }
            needAppendNode = newNode;
        }

        if (needInsertNode == null) {
            lastNode = needAppendNode;
        } else {
            needAppendNode.nextNode = needInsertNode;
            needInsertNode.preNode = needAppendNode;
        }

        size += numNew;
        return true;
    }

    @Override
    public boolean offerFirst(T t) {
        addFirst(t);
        return true;
    }

    @Override
    public boolean offerLast(T t) {
        addLast(t);
        return true;
    }

    @Override
    public T set(int index, T element) {
        checkIndexForAdd(index);
        MyLinkedList.Node<T> x = node(index);
        T oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    @Override
    public T removeFirst() {
        Node<T> lastFirst = firstNode;
        if (lastFirst == null) {
            throw new NoSuchElementException();
        }
        Node<T> newFirst = lastFirst.nextNode;
        if (newFirst == null) {
            firstNode = null;
            lastNode = null;
        } else {
            newFirst.preNode = null;
            firstNode = newFirst;
        }
        size--;
        return lastFirst.item;
    }

    @Override
    public T removeLast() {
        Node<T> lastLast = lastNode;
        if (lastLast == null) {
            throw new NoSuchElementException();
        }
        Node<T> newLast = lastLast.preNode;
        if (newLast == null) {
            firstNode = null;
            lastNode = null;
        } else {
            newLast.nextNode = null;
            lastNode = newLast;
        }
        size--;
        return lastLast.item;
    }

    @Override
    public T pollFirst() {
        return firstNode == null ? null : removeFirst();
    }

    @Override
    public T pollLast() {
        return lastNode == null ? null : removeLast();
    }

    @Override
    public T getFirst() {
        return firstNode == null ? null : firstNode.item;
    }

    @Override
    public T getLast() {
        return lastNode == null ? null : lastNode.item;
    }

    @Override
    public T peekFirst() {
        return firstNode == null ? null : firstNode.item;
    }

    @Override
    public T peekLast() {
        return lastNode == null ? null : lastNode.item;
    }

    @Override
    public boolean removeFirstOccurrence(Object o) {
        if (o == null) {
            for (Node<T> node = firstNode; node != null; node = node.nextNode) {
                if (node.item == null) {
                    unlink(node);
                    return true;
                }
            }
        } else {
            for (Node<T> node = firstNode; node != null; node = node.nextNode) {
                if (node.item == null) {
                    unlink(node);
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            for (Node<T> node = lastNode; node != null; node = node.preNode) {
                if (node.item == null) {
                    unlink(node);
                    return true;
                }
            }
        } else {
            for (Node<T> node = lastNode; node != null; node = node.preNode) {
                if (node.item == null) {
                    unlink(node);
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean offer(T t) {
        return add(t);
    }

    @Override
    public T remove() {
        return removeFirst();
    }

    @Override
    public boolean remove(Object t) {
        for (Node<T> node = firstNode; node.nextNode != null; node = node.nextNode) {
            if (Objects.equals(t, node.item)) {
                unlink(node);
                return true;
            }
        }
        return false;
    }

    @Override
    public T remove(int index) {
        checkIndexForGet(index);
        return unlink(node(index));
    }

    @Override
    public T poll() {
        return firstNode == null ? null : unlink(firstNode);
    }

    @Override
    public T element() {
        return getFirst();
    }

    @Override
    public T peek() {
        return peekFirst();
    }

    @Override
    public void push(T t) {
        addFirst(t);
    }

    @Override
    public T pop() {
        return removeFirst();
    }

    @Override
    public Iterator<T> descendingIterator() {
        return null;
    }

    @Override
    public int indexOf(Object o) {
        int index = 0;
        for (Node<T> node = firstNode; node.nextNode != null; node = node.nextNode, index++) {
            if (Objects.equals(node.item, o)) {
                return index;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        int index = size() - 1;
        for (Node<T> node = lastNode; node.preNode != null; node = node.preNode, index--) {
            if (Objects.equals(node.item, o)) {
                return index;
            }
        }
        return index;
    }

    T unlink(MyLinkedList.Node<T> node) {
        if (node.preNode == null) {
            firstNode = node.nextNode;
        } else {
            node.preNode.nextNode = node.nextNode;
        }

        if (node.nextNode == null) {
            lastNode = node.preNode;
        } else {
            node.nextNode.preNode = node.preNode;
        }
        T item = node.item;
        node.item = null;
        size--;
        return item;
    }

    Node<T> node(int index) {
        if (index < (size >> 1)) {
            //index 小于size一半从前面开始数
            Node<T> result = firstNode;
            for (int i = 0; i < index; i++) {
                result = result.nextNode;
            }
            return result;
        } else {
            Node<T> result = lastNode;
            for (int i = size - 1; i > index; i--) {
                result = result.preNode;
            }
            return result;
        }
    }

    void checkIndexForAdd(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index:" + index + ",size:" + size);
        }
    }

    void checkIndexForGet(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("index:" + index + ",size:" + size);
        }
    }

    @AllArgsConstructor
    private static class Node<T> {
        /**
         * 真实的元素
         */
        private T item;
        /**
         * 上一个节点
         */
        private Node<T> preNode;
        /**
         * 下一个节点
         */
        private Node<T> nextNode;
    }

    private class ListItr implements ListIterator<T> {
        /**
         * 上一次返回的节点
         */
        private MyLinkedList.Node<T> lastReturned;
        /**
         * 下一个节点
         */
        private MyLinkedList.Node<T> nextNode;
        /**
         * 下一个节点的index
         */
        private int nextIndex;

        ListItr(int index) {
            checkIndexForGet(index);
            nextNode = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            lastReturned = nextNode;
            nextNode = nextNode.nextNode;
            nextIndex++;
            return lastReturned.item;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public T previous() {
            if (!hasPrevious()) {
                throw new NoSuchElementException();
            }

            lastReturned = nextNode = (nextNode == null) ? null : nextNode.preNode;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }

            Node<T> lastNext = lastReturned.nextNode;
            unlink(lastReturned);
            if (nextNode == lastReturned) {
                nextNode = lastNext;
            } else {
                nextIndex--;
            }
            lastReturned = null;
        }

        public void set(T t) {
            if (lastReturned == null) {
                throw new IllegalStateException();
            }
            lastReturned.item = t;
        }

        public void add(T t) {
            Node<T> node;
            lastReturned = null;
            if (nextNode != null) {
                Node<T> newNode = new Node<T>(t, nextNode.preNode, nextNode);
                nextNode.preNode.nextNode = newNode;
                nextNode.preNode = newNode;
            } else {
                addLast(t);
            }
            nextIndex++;
            MyLinkedList.this.size++;
        }

        public void forEachRemaining(Consumer<? super T> action) {
            Objects.requireNonNull(action);
            while (nextIndex < size) {
                action.accept(nextNode.item);
                lastReturned = nextNode;
                nextNode = nextNode.nextNode;
                nextIndex++;
            }
        }
    }
}
